#include "filesys/inode.h"
#include <list.h>
#include <debug.h>
#include <round.h>
#include <string.h>
#include "filesys/cache.h"
#include "threads/malloc.h"
#include "filesys/filesys.h"
#include "filesys/free-map.h"

#define INODE_MAGIC 0x494e4f44    /* Identifies an inode. */
#define MAX_DBLOCKS 122
#define MAX_SIBLOCKS 122 + 128

/* On-disk inode.
   Must be exactly BLOCK_SECTOR_SIZE bytes long. */
struct inode_disk
{
  off_t length;                       /* File size in bytes. */
  off_t end;                          /* File end offset in bytes */
  unsigned magic;                     /* Magic number. */
  block_sector_t dblock[122];         /* Direct blocks */
  block_sector_t iblock[2];           /* Indirect blocks */
  bool isdir;                         /* Directory/file flag */ 
};

/* Returns the number of sectors to allocate for an inode SIZE
   bytes long. */
static inline size_t
bytes_to_sectors (off_t size)
{
  return DIV_ROUND_UP (size, BLOCK_SECTOR_SIZE);
}

/* In-memory inode. */
struct inode 
{
  struct list_elem elem;              /* Element in inode list. */
  block_sector_t sector;              /* Sector number of disk location. */
  int open_cnt;                       /* Number of openers. */
  bool removed;                       /* True if deleted, false otherwise. */
  int deny_write_cnt;                 /* 0: writes ok, >0: deny writes. */
  struct inode_disk data;             /* Inode content. */  
  struct lock growth_lock;            /* Index node growth lock */
};

/* Function declarations */
static block_sector_t inode_allocate_dblock (block_sector_t*);
static block_sector_t inode_allocate_iblock (block_sector_t*, int);
static bool inode_grow (struct inode*, off_t);
static block_sector_t byte_to_sector (const struct inode*, off_t);
static void inode_set_length (const struct inode*, off_t);

/* Allocate a block sector number from the free map pool if one is */
/* available, otherwise return -1 */
static block_sector_t
inode_allocate_dblock (block_sector_t *block)
{
  block_sector_t sector_idx = INVALID_SECTOR_IDX;
  if (free_map_allocate (1, &sector_idx))
    cache_write (sector_idx, block, 0, BLOCK_SECTOR_SIZE);

  return sector_idx;
}

/* Allocate multiple block numbers from the free map pool for an indirect */
/* block at once. Block number allocation is done via an explicit call to */
/* inode_allocate_dblock. Returns -1 if no block numbers remain in the */
/* free map pool */
static block_sector_t
inode_allocate_iblock (block_sector_t *block, int index)
{
  block_sector_t sector_idx = INVALID_SECTOR_IDX;
  /* Allocate 512 bytes of memory from the heap */
  block_sector_t *iblock = calloc (1, BLOCK_SECTOR_SIZE);
  int i;

  for (i = 0; i < index; i++)
    iblock[i] = inode_allocate_dblock (block);
  sector_idx = inode_allocate_dblock (iblock);

  if (iblock)
    free (iblock);

  return sector_idx;
}

/* Expand the file when the offset to be written to is beyond the current */
/* end-of-file */
static bool
inode_grow (struct inode *inode, off_t pos)
{
  /* (1) 'inode_meta' represents an inode_disk structure representing */
  /*     a file's metadata (in this case) */
  /* (2) 'sind_block' represents a single indirect block which is used */
  /*     for storing 128 additional direct blocks */
  /* (3) 'dind_block' represents a double indirect block which is used */
  /*     for storing 128 single indirect blocks */
  /* (4) 'null_block' is an empty block. It does not hold any data and is */
  /*     saved to disk for an allocated block number until 'inode_write_at' */
  /*     writes some actual data to the expanded file's block numbers */

  struct inode_disk *inode_meta;
  block_sector_t *sind_block, *dind_block, *null_block;
  inode_meta = sind_block = dind_block = null_block = NULL;

  inode_meta = malloc (sizeof (struct inode_disk));
  if (!inode_meta)
    return INVALID_SECTOR_IDX;
  sind_block = calloc (1, BLOCK_SECTOR_SIZE);
  if (!sind_block)
    return INVALID_SECTOR_IDX;
  dind_block = calloc (1, BLOCK_SECTOR_SIZE);
  if (!dind_block)
    return INVALID_SECTOR_IDX;
  null_block = calloc (1, BLOCK_SECTOR_SIZE);
  if (!null_block)
    return INVALID_SECTOR_IDX;

  /* Read file's meta data from the file system cache */
  cache_read (inode->sector, inode_meta, 0, BLOCK_SECTOR_SIZE);
  int pos_sector = pos / BLOCK_SECTOR_SIZE;  
  int end_sector = -1;
  if (inode_meta->end >= 0)
    end_sector = inode_meta->end / BLOCK_SECTOR_SIZE;

  /* If the current end-of-file is less than the offset, expand the file */
  if (inode_meta->end < pos)
  {
    /* Level 1 of expansion: Direct block allocation */
    if (end_sector < MAX_DBLOCKS - 1)
    {
      int i;
      for (i = (end_sector + 1); i < MAX_DBLOCKS && i <= pos_sector; i++)
        inode_meta->dblock[i] = inode_allocate_dblock (null_block);
      end_sector = i - 1;
    }
    /* Level 2 of expansion: Single indirect block allocation */
    if (end_sector < pos_sector)
    {
      int index = 128;
      if (pos_sector - MAX_DBLOCKS + 1 < 128)
        index = pos_sector - MAX_DBLOCKS + 1;

      if (inode_meta->iblock[0] == INVALID_SECTOR_IDX)
        inode_meta->iblock[0] = inode_allocate_iblock (null_block, index);
      else
      {
        cache_read (inode_meta->iblock[0], sind_block, 0, BLOCK_SECTOR_SIZE);
        
        int i;
        for (i = (end_sector + 1); i < MAX_SIBLOCKS && i <= pos_sector; i++)
          sind_block[i - MAX_DBLOCKS] = inode_allocate_dblock (null_block);

        cache_write (inode_meta->iblock[0], sind_block, 0, BLOCK_SECTOR_SIZE);
      }
      end_sector = (MAX_SIBLOCKS - 1) < pos_sector ?
                   (MAX_SIBLOCKS - 1) : pos_sector;
    }
    /* Level 3 of exapnsion: Double indirect block allocation */
    if (end_sector < pos_sector)
    {
      /* Single indirect block number within the double indirect block */
      int sib_num = (((pos / BLOCK_SECTOR_SIZE) - MAX_DBLOCKS) / 128) - 1;
      /* Direct block number within the single indirect number given by */
      /* 'sub_num' above */
      int db_num = ((pos / BLOCK_SECTOR_SIZE) - MAX_DBLOCKS) % 128;

      if (inode_meta->iblock[1] == INVALID_SECTOR_IDX)
      {
        int i;
        for (i = 0; i < sib_num; i++)
          dind_block[i] = inode_allocate_iblock (null_block, 128);
        dind_block[sib_num] = inode_allocate_iblock (null_block, db_num + 1);
        
        inode_meta->iblock[1] = inode_allocate_dblock (dind_block);
        end_sector = pos_sector;
      }
      else
      {
        /* Read the double indirect block's meta data into 'dind_block' */
        cache_read (inode_meta->iblock[1], dind_block, 0, BLOCK_SECTOR_SIZE);

        int i, j;
        for (i = 0; i < 128 && i <= sib_num; i++)
        {
          while (dind_block[i] == 0 && i <= sib_num)
          {
            if (i < sib_num)
              dind_block[i] = inode_allocate_iblock (null_block, 128);
            else
            {
              dind_block[sib_num] = inode_allocate_iblock
                                    (null_block, db_num + 1);
              goto DONE;
            }
              
            i++;
          }

          /* Access the single indirect block at this offset and read its */
          /* meta data into 'sind_block' */
          cache_read (dind_block[i], sind_block, 0, BLOCK_SECTOR_SIZE);

          if (i < sib_num)
          {
            for (j = 0; j < 128; j++)
            { 
              if (sind_block[j] == 0)
                sind_block[j] = inode_allocate_dblock (null_block);
            }
          }
          else
          {
            for (j = 0; j <= db_num; j++)
            {
              if (sind_block[j] == 0)
                sind_block[j] = inode_allocate_dblock (null_block);
            }
          }

          /* Write the updated meta data for the single indirect block back */
          /* to the file system cache */
          cache_write (dind_block[i], sind_block, 0, BLOCK_SECTOR_SIZE);
        }

        DONE:
        /* Write the updated meta data for the double indirect block back */
        /* to the file system cache */
        cache_write (inode_meta->iblock[1], dind_block, 0, BLOCK_SECTOR_SIZE);
      }
    }
  }
  
  /* Update the end offset and the length for this inode_disk */
  inode_meta->end = pos;
  if (inode_meta->length < inode_meta->end)
    inode_meta->length = inode_meta->end;

  /* Write the inode_disk back to the file system cache */
  cache_write (inode->sector, inode_meta, 0, BLOCK_SECTOR_SIZE);
  
  if (null_block)
    free (null_block);
  if (dind_block)
    free (dind_block);
  if (sind_block)
    free (sind_block);
  if (inode_meta)
    free (inode_meta);

  return true;
}

/* Returns the block device sector that contains byte offset POS
   within INODE.
   Returns -1 if INODE does not contain data for a byte at offset
   POS. */
static block_sector_t
byte_to_sector (const struct inode *inode, off_t pos)
{
  ASSERT (inode != NULL);
  
  struct inode_disk *inode_meta;
  block_sector_t *sind_block, *dind_block;
  inode_meta = sind_block = dind_block = NULL;
  block_sector_t pos_sector = INVALID_SECTOR_IDX;

  inode_meta = malloc (sizeof (struct inode_disk));
  if (!inode_meta)
    return INVALID_SECTOR_IDX;
  sind_block = calloc (1, BLOCK_SECTOR_SIZE);
  if (!sind_block)
    return INVALID_SECTOR_IDX;
  dind_block = calloc (1, BLOCK_SECTOR_SIZE);
  if (!dind_block)
    return INVALID_SECTOR_IDX;

  /* Read inode's metadata from the file system cache */
  cache_read (inode->sector, inode_meta, 0, BLOCK_SECTOR_SIZE);
  
  /* If the current end-of-file is less that the offset being accessed, */
  /* then expand the file */
  if (inode_meta->end < pos)
  {
    lock_acquire (&inode->growth_lock);
    inode_grow (inode, pos);
    lock_release (&inode->growth_lock);
  }
  
  /* Read the expanded file's meta data from the disk */
  cache_read (inode->sector, inode_meta, 0, BLOCK_SECTOR_SIZE);
  /* Direct block region */
  if ((pos / BLOCK_SECTOR_SIZE) < MAX_DBLOCKS)
    pos_sector = inode_meta->dblock[pos / BLOCK_SECTOR_SIZE];
  /* Single indirect block region */
  else if ((pos / BLOCK_SECTOR_SIZE) < MAX_SIBLOCKS)
  {
    int index = (pos / BLOCK_SECTOR_SIZE) - MAX_DBLOCKS;
    cache_read (inode_meta->iblock[0], sind_block, 0, BLOCK_SECTOR_SIZE);
    pos_sector = sind_block[index];
  }
  /* Double indirect block region */
  else
  {
    int sib_num = (((pos / BLOCK_SECTOR_SIZE) - MAX_DBLOCKS) / 128) - 1;
    int db_num = ((pos / BLOCK_SECTOR_SIZE) - MAX_DBLOCKS) % 128;
    
    cache_read (inode_meta->iblock[1], dind_block, 0, BLOCK_SECTOR_SIZE);
    cache_read (dind_block[sib_num], sind_block, 0, BLOCK_SECTOR_SIZE);
    pos_sector = sind_block[db_num];
  }
  
  if (dind_block)
    free (dind_block);
  if (sind_block)
    free (sind_block);
  if (inode_meta)
    free (inode_meta);

  return pos_sector;
}

/* List of open inodes, so that opening a single inode twice
   returns the same `struct inode'. */
static struct list open_inodes;

/* Initializes the inode module. */
void
inode_init (void) 
{
  list_init (&open_inodes);
}

/* Initializes an inode with ZERO bytes of data and
   writes the new inode to sector SECTOR on the file system
   device.
   Returns true if successful.
   Returns false if memory or disk allocation fails. */
bool
inode_create (block_sector_t sector, off_t length, bool isdir)
{
  struct inode_disk *disk_inode = NULL;
  ASSERT (length >= 0);

  /* If this assertion fails, the inode structure is not exactly
     one sector in size, and you should fix that. */
  ASSERT (sizeof *disk_inode == BLOCK_SECTOR_SIZE);

  disk_inode = calloc (1, sizeof *disk_inode);
  if (disk_inode != NULL)
  {
    /* Special handler for the free map creation */
    if (sector == FREE_MAP_SECTOR)
    {
      static char zeros[BLOCK_SECTOR_SIZE];  /* Placeholder data */     
 
      disk_inode->end = length;
      disk_inode->dblock[0] = FREE_DATA_SECTOR;
      cache_write (FREE_DATA_SECTOR, zeros, 0, BLOCK_SECTOR_SIZE);
    }
    else
    {
      disk_inode->end = -1;
      
      int i;
      for (i = 0; i < MAX_DBLOCKS; i++)
        disk_inode->dblock[i] = -1;
      for (i = 0; i < 2; i++)
        disk_inode->iblock[i] = -1;
    }

    disk_inode->length = length;
    disk_inode->magic = INODE_MAGIC;
    disk_inode->isdir = isdir;
    

    /* Write the file's meta data to file system cache and perform clean up */
    cache_write (sector, disk_inode, 0, BLOCK_SECTOR_SIZE);
    free (disk_inode);
  }
  
  return true;
}

/* Reads an inode from SECTOR
   and returns a `struct inode' that contains it.
   Returns a null pointer if memory allocation fails. */
struct inode *
inode_open (block_sector_t sector)
{
  struct list_elem *e;
  struct inode *inode;

  /* Check whether this inode is already open. */
  for (e = list_begin (&open_inodes); e != list_end (&open_inodes);
       e = list_next (e)) 
    {
      inode = list_entry (e, struct inode, elem);
      if (inode->sector == sector) 
        {
          inode_reopen (inode);
          return inode; 
        }
    }

  /* Allocate memory. */
  inode = malloc (sizeof *inode);
  if (inode == NULL)
    return NULL;

  /* Initialize. */
  list_push_front (&open_inodes, &inode->elem);
  inode->sector = sector;
  inode->open_cnt = 1;
  inode->deny_write_cnt = 0;
  inode->removed = false;
  lock_init (&inode->growth_lock);
  cache_read (inode->sector, &inode->data, 0, BLOCK_SECTOR_SIZE);
  
  return inode;
}

/* Reopens and returns INODE. */
struct inode *
inode_reopen (struct inode *inode)
{
  if (inode != NULL)
    inode->open_cnt++;
  return inode;
}

/* Returns INODE's inode number. */
block_sector_t
inode_get_inumber (const struct inode *inode)
{
  return inode->sector;
}

/* Closes INODE and writes it to disk.
   If this was the last reference to INODE, frees its memory.
   If INODE was also a removed inode, frees its blocks. */
void
inode_close (struct inode *inode) 
{
  /* Ignore null pointer. */
  if (inode == NULL)
    return;

  /* Release resources if this was the last opener. */
  if (--inode->open_cnt == 0)
    {
      /* Remove from inode list and release lock. */
      list_remove (&inode->elem);
 
      /* Deallocate blocks if removed. */
      if (inode->removed)
      {
        struct inode_disk *inode_meta;
        block_sector_t *sind_block, *dind_block;
        inode_meta = sind_block = dind_block = NULL;
        
        inode_meta = malloc (sizeof (struct inode_disk));        
        if (!inode_meta)
          return;
        sind_block = calloc (1, BLOCK_SECTOR_SIZE);
        if (!sind_block)
          return;
        dind_block = calloc (1, BLOCK_SECTOR_SIZE);
        if (!dind_block)
          return;

        free_map_release (inode->sector, 1);

        cache_read (inode->sector, inode_meta, 0, BLOCK_SECTOR_SIZE);
        int end_sector = -1;
        if (inode_meta->end >= 0)
          end_sector = inode_meta->end / BLOCK_SECTOR_SIZE;

        if (end_sector >= 0)
        {
          /* Release direct blocks */
          int i;
          for (i = 0; i < MAX_DBLOCKS && i <= end_sector; i++)
            free_map_release (inode_meta->dblock[i], 1);
          
          /* Release single indirect blocks */
          if (end_sector >= MAX_DBLOCKS)
          {
            cache_read (inode_meta->iblock[0], sind_block,
                        0, BLOCK_SECTOR_SIZE);
            for (i = 0; i < 128 && i <= (end_sector - MAX_DBLOCKS); i++)
              free_map_release (sind_block[i], 1);
            free_map_release (inode_meta->iblock[0], 1);
          }
          
          /* Release double indirect blocks */
          if (end_sector >= MAX_SIBLOCKS)
          {
            cache_read (inode_meta->iblock[1], dind_block,
                        0, BLOCK_SECTOR_SIZE);
            for (i = 0; i < 128; i++)
            {
              if (dind_block[i] == INVALID_SECTOR_IDX)
                break;
              
              int j;
              cache_read (dind_block[i], sind_block, 0, BLOCK_SECTOR_SIZE);
              for (j = 0; j < MAX_DBLOCKS
                          && j <= (end_sector - MAX_SIBLOCKS); j++)
                free_map_release (sind_block[i], 1);
              free_map_release (dind_block[i], 1);
            }
            free_map_release (inode_meta->iblock[1], 1);
          }
        }

        if (dind_block)
          free (dind_block);
        if (sind_block)
          free (sind_block);
        if (inode_meta)
          free (inode_meta);
      }

      free (inode); 
    }
}

/* Marks INODE to be deleted when it is closed by the last caller who
   has it open. */
void
inode_remove (struct inode *inode) 
{
  ASSERT (inode != NULL);
  inode->removed = true;
}

/* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
   Returns the number of bytes actually read, which may be less
   than SIZE if an error occurs or end of file is reached. */
off_t
inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset) 
{
  uint8_t *buffer = buffer_;
  off_t bytes_read = 0;

  if (offset >= inode_length (inode))
    return 0;

  while (size > 0) 
    {
      /* Disk sector to read, starting byte offset within sector. */
      block_sector_t sector_idx = byte_to_sector (inode, offset);
      if (sector_idx == INVALID_SECTOR_IDX)
        break;
      int sector_ofs = offset % BLOCK_SECTOR_SIZE;

      /* Bytes left in inode, bytes left in sector, lesser of the two. */
      off_t inode_left = inode_length (inode) - offset;
      int sector_left = BLOCK_SECTOR_SIZE - sector_ofs;
      int min_left = inode_left < sector_left ? inode_left : sector_left;

      /* Number of bytes to actually copy out of this sector. */
      int chunk_size = size < min_left ? size : min_left;
      if (chunk_size <= 0)
        break;

      /* Read from file system cache */
      cache_read (sector_idx, buffer + bytes_read, sector_ofs, chunk_size);
      
      /* Advance. */
      size -= chunk_size;
      offset += chunk_size;
      bytes_read += chunk_size;
    }

  return bytes_read;
}

/* Writes SIZE bytes from BUFFER into INODE, starting at OFFSET.
   Returns the number of bytes actually written, which may be
   less than SIZE if end of file is reached or an error occurs.
   (Normally a write at end of file would extend the inode, but
   growth is not yet implemented.) */
off_t
inode_write_at (struct inode *inode, const void *buffer_, off_t size,
                off_t offset) 
{
  const uint8_t *buffer = buffer_;
  off_t bytes_written = 0;

  if (inode->deny_write_cnt)
    return 0;

  while (size > 0) 
    {
      /* Sector to write, starting byte offset within sector. */
      block_sector_t sector_idx = byte_to_sector (inode, offset);
      int sector_ofs = offset % BLOCK_SECTOR_SIZE;

      /* Bytes left in inode, bytes left in sector, lesser of the two. */
      off_t inode_left = BLOCK_SECTOR_SIZE;
      int sector_left = BLOCK_SECTOR_SIZE - sector_ofs;
      int min_left = inode_left < sector_left ? inode_left : sector_left;

      /* Number of bytes to actually write into this sector. */
      int chunk_size = size < min_left ? size : min_left;
      if (chunk_size <= 0)
        break;

      /* Write to file system cache */
      cache_write (sector_idx, buffer + bytes_written, sector_ofs, chunk_size);

      /* Advance. */
      size -= chunk_size;
      offset += chunk_size;
      bytes_written += chunk_size;
    }
  
  inode_set_length (inode, offset + size);
  return bytes_written;
}

/* Disables writes to INODE.
   May be called at most once per inode opener. */
void
inode_deny_write (struct inode *inode) 
{
  inode->deny_write_cnt++;
  ASSERT (inode->deny_write_cnt <= inode->open_cnt);
}

/* Re-enables writes to INODE.
   Must be called once by each inode opener who has called
   inode_deny_write() on the inode, before closing the inode. */
void
inode_allow_write (struct inode *inode) 
{
  ASSERT (inode->deny_write_cnt > 0);
  ASSERT (inode->deny_write_cnt <= inode->open_cnt);
  inode->deny_write_cnt--;
}

/* Returns the length, in bytes, of INODE's data. */
off_t
inode_length (const struct inode *inode)
{
  struct inode_disk *inode_meta = malloc (sizeof (struct inode_disk));
  if (!inode_meta)
    return -1;

  cache_read (inode->sector, inode_meta, 0, BLOCK_SECTOR_SIZE);
  off_t length = inode_meta->length;

  if (inode_meta)
    free (inode_meta);

  return length;
}

/* Update the file's length in its metadata upon extension */
static void
inode_set_length (const struct inode *inode, off_t size)
{
  struct inode_disk *inode_meta = malloc (sizeof (struct inode_disk));
  if (!inode_meta)
    return;

  cache_read (inode->sector, inode_meta, 0, BLOCK_SECTOR_SIZE);
  inode_meta->length = inode_meta->length > size ?
                       inode_meta->length : size;
  cache_write (inode->sector, inode_meta, 0, BLOCK_SECTOR_SIZE);

  if (inode_meta)
    free (inode_meta);
}

bool 
inode_get_isdir (struct inode *inode)
{
  if (inode == NULL)
      return false;
  else
      return inode->data.isdir;
}

int 
inode_get_open_count (struct inode *inode)
{
  return inode->open_cnt;
}

void
inode_incr_open_cnt (struct inode *inode)
{
  ASSERT (inode != NULL);
  inode->open_cnt++;
}
